package com.mid;

import java.util.Arrays;

/**
 * Created by Lxk on 2020/2/12.
 */
public class Solution213 {

    /**
     * dp求解：
     * 相比之前的打家劫舍初版本，这个增加了对于最后一个元素和第一个元素的关联限制，
     * 可以在初级版本的基础上增加判断逻辑；
     * 令dp[i]为到i位置为止，可以收获赃物最大价值
     * 则i位置的最大价值可以由两种方式的比较得来
     * 1、如果打劫i-1,则dp[i] = dp[i-1]
     * 2、如果不打劫i-1,则dp[i] = dp[i-2] + val[i]
     * 3、针对于最后一个元素的值，如果当前第一个元素已经获取，则最后一个元素不能取；反之亦然
     * 针对3中的情况，可以分为[0,n-1]和[1,n]两次计算，即舍弃最后一个和第一个
     * <p>
     * 讨论不可能存在舍弃第一个时，最后一个元素没取，需要补上第一个的情况
     * 以及舍弃最后一个时，第一个元素没取，需要补上的情况
     * 假设存在，以舍弃位置1为例，则必然为1,{2,[3,,,,,,n-2,n-1],n}
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(robHelp(Arrays.copyOfRange(nums, 0, nums.length - 1)), robHelp(Arrays.copyOfRange(nums, 1, nums.length)));
    }

    private int robHelp(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int preMax = nums[0], max = 0, prePreMax = 0;
        boolean flag = false;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(prePreMax + nums[i], preMax);
            prePreMax = preMax;
            preMax = max;
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 6, 2};
        Solution213 solution213 = new Solution213();
        System.out.println(solution213.rob(arr));
    }

}
